//
// Description: 78. 子集
// Created by Loading on 2021/4/23.
//

#include <bits/stdc++.h>

using namespace std;

/* 抽象0/1序列二进制迭代 */
vector<vector<int>> subsets(vector<int> &nums) {
    int n = nums.size();
    vector<vector<int>> res;
    //将nums比作一个长度为n的二进制数，则这个二进制数必然小于 1 << n
    //从0开始，遍历至 (1 << n) - 1，其中的0代表未选中，1代表选中，枚举选取
    for (int i = 0; i < (1 << n); ++i) {
        vector<int> vec;
        //每个抽象出来的二进制数，长度都是n
        for (int j = 0; j < n; ++j) {
            //对每一位，如果是1，则选中，加入集合中
            if (1 << j & i) {
                vec.emplace_back(nums[j]);
            }
        }
        res.emplace_back(vec);
    }

    return res;
}

/* dfs递归回溯 */
void dfs(int cur, vector<int>& vec, vector<int> &nums, vector<vector<int>> &res){
    //位置遍历至nums长度，结束
    if(cur == nums.size()){
        res.emplace_back(vec);
        return;
    }
    //假设该位置选中，继续向后遍历
    vec.emplace_back(nums[cur]);
    dfs(cur + 1, vec, nums, res);
    //假设该位置未选中，继续向后遍历
    vec.pop_back();
    dfs(cur + 1, vec, nums, res);
}

vector<vector<int>> subsets_dfs(vector<int> &nums) {
    vector<int> vec;
    vector<vector<int>> res;
    //参数：1、当前位置 2、回溯数组 3、nums数组 4、结果数组
    dfs(0, vec, nums, res);

    return res;
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> res = subsets(nums);
    for (auto &v : res) {
        for (auto &x : v) {
            cout << x << " ";
        }
        cout << endl;
    }

    vector<vector<int>> res_dfs = subsets_dfs(nums);
    for (auto &v : res_dfs) {
        for (auto &x : v) {
            cout << x << " ";
        }
        cout << endl;
    }
}